Algorithmathon Single Linked List Base

Created: 14 July 2013  Modified:

Below is the code to be used as the base starting with Day 2 of the Algorithmathon. We have our RSpec test along with our Single Linked List (SLL) Element and the SLL itself. This code will be used as the starting point for most of the Algorithms involving SLL. The code for which can be found on GitHub.

single_linked_list_element_spec.rb

require 'spec_helper'

describe SingleLinkedListElement do
  describe "Class" do
    it "should have a 'next_node' method" do
      SingleLinkedListElement.method_defined?(:next_node).should be_true
    end
    it "should have a 'data' method" do
      SingleLinkedListElement.method_defined?(:data).should be_true
    end

  end
end

single_linked_list_spec.rb

require 'spec_helper'
require 'single_linked_list_spec_helper'

describe SingleLinkedList do

  describe "Class" do
    it "should have method 'last'" do
      SingleLinkedList.method_defined?(:last).should be_true
    end

    it "should have method 'add'" do
      SingleLinkedList.method_defined?(:add).should be_true
    end

    it "should have method 'length'" do
      SingleLinkedList.method_defined?(:length).should be_true
    end    
  end

  describe "Instance" do

    before(:each) do
      @list = SingleLinkedList.new()
    end

    it "should return nil when 'last()' is called" do
      @list.last().should be_nil
    end

    it "should not return nil when 'last()' is called" do
      add_elements(@list)
      @list.last().should_not be_nil
    end
    
    it "should return 'four' when 'last().data' is called" do
      add_elements(@list)
      @list.last().data.should == "four"
    end 

     it "should return 4 when 'length' is called" do
      add_elements(@list)
      @list.length().should == 4
    end   

  end

end

single_linked_list_element.rb

class SingleLinkedListElement
  attr_accessor :next_node, :data

  def initialize(data=nil,next_node=nil)
    self.data=data
    self.next_node=next_node
  end
en

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :head

  def add(element)
    if @head.nil?
      @head = element
    else
      last_element=last()
      last_element.next_node=element
    end
  end

  def last()
    last_element=SingleLinkedListElement.new()
    last_by_recursion(@head,last_element)
    last_element.next_node
  end 

  def length()
    length_by_recursion(@head,0)
  end  

  private
    def last_by_recursion(element,last_element)
      unless element.nil?
        last_element.next_node=element
        unless element.next_node.nil?
          last_by_recursion(element.next_node,last_element)
        end
      end
    end

    def length_by_recursion(element,count)
      unless element.nil?
        count = count + 1
        length_by_recursion(element.next_node,count)
      else
        count
      end
    end    
end
tags: Algorithm - Algorithmathon - RSpec - Ruby - Single Linked List
   Less Is More